package string;

/**
 * O(m+n),tested
 * 
 * @author yinzichen
 * 
 */
public class KMP {

	public int[] buildNext(String needle) {
		int m = needle.length();
		int[] next = new int[m];
		next[0] = -1;
		int i = -1, j = 1;
		while (j < m) {
			if (i < 0 || needle.charAt(i) == needle.charAt(j - 1)) {
				next[j++] = ++i;
			} else {
				i = next[i];
			}
		}
		return next;
	}

	public String strStr(String haystack, String needle) {
		int n = haystack.length(), m = needle.length();
		if (m == 0)
			return haystack;
		else if (n < m)
			return null;
		int[] next = buildNext(needle);
		int i = 0, j = 0;
		while (i < n && j < m) {
			if (n - i < m - j)
				return null;
			if (j < 0 || haystack.charAt(i) == needle.charAt(j)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
		}
		return haystack.substring(i - m);
	}

}
